package com.beck.bee.leetcode;

/**
 * Created by cdliubei@jd.com on 4/13/2017.
 */
public class Main {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null){
            return root;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null){
            return true;
        }
        ListNode p = new ListNode(0);
        p.next = head;
        ListNode slow = p;
        ListNode fast = p;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode pre = null;
        ListNode cur = slow.next;
        slow.next = null;
        ListNode last = cur.next;
        while (last != null){
            ListNode temp = last.next;
            cur.next = pre;
            pre = cur;
            cur = last;
            last = temp;
        }
        cur.next = pre;
        ListNode inverseHead = cur;
        while (head != null && inverseHead != null){
            if (head.val == inverseHead.val){
                head = head.next;
                inverseHead = inverseHead.next;
            }else {
                return false;
            }
        }
        return true;
    }

    public void test(){
        ListNode p1 = new ListNode(1);
        ListNode p2 = new ListNode(4);
        ListNode p3 = new ListNode(-1);
        ListNode p4 = new ListNode(-1);
        ListNode p5 = new ListNode(4);
        ListNode p6 = new ListNode(1);
        p1.next = p2;
        p2.next = p3;
        p3.next = p4;
        p4.next = p5;
        p5.next = p6;
        System.out.print(isPalindrome(p1));
    }

    public static void main(String[] args) {
        Main main = new Main();
        main.test();
    }

}
